package com.exercises;


import com.alibaba.fastjson.JSONObject;

import java.util.HashMap;
import java.util.Map;

class Exercise138 {
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    static Map<Node, Node> map = new HashMap<>();

    public static void main(String[] args) {
        Node n7 = new Node(7);
        Node n13 = new Node(13);
        Node n11 = new Node(11);
        Node n10 = new Node(10);
        Node n1 = new Node(1);
        n7.next = n13;
        n13.next = n11;
        n11.next = n10;
        n10.next = n1;
        n13.random = n7;
        n11.random = n1;
        n10.random = n11;
        n1.random = n7;

        copyRandomList(n7);
    }


    public static Node copyRandomList(Node head) {
        return dfs(head);
    }

    public static Node dfs(Node n) {
        if (n == null) return null;
        System.out.println(n.val);
        if (map.containsKey(n)) return map.get(n);
        Node copy = new Node(n.val);
        map.put(n, copy);
        copy.next = dfs(n.next);
        copy.random = dfs(n.random);

        return copy;
    }
}
